package leetcodev1.树;

import java.util.ArrayList;
import java.util.List;

public class LeetCode113 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ret = new ArrayList<>();
        dfs(ret, new ArrayList<>(), targetSum, root);
        return ret;
    }

    private void dfs(List<List<Integer>> ret, List<Integer> router, int targetSum, TreeNode node) {
        if (node == null) {
            return;
        }

        if (targetSum == node.val && node.left == null && node.right == null) {
            List<Integer> tmp = new ArrayList<>(router);
            tmp.add(node.val);
            ret.add(tmp);
            return;
        }

        router.add(node.val);
        dfs(ret, router, targetSum - node.val, node.left);
        dfs(ret, router, targetSum - node.val, node.right);
        router.remove(router.size() - 1);
    }
}
